|
The phi-hiding assumption or Φ-hiding assumption is an assumption about the difficulty of finding small factors of φ(''m'') where ''m'' is a number whose factorization is unknown, and φ is Euler's totient function. The security of many modern cryptosystems comes from the perceived difficulty of certain problems. Since P vs. NP problem is still unresolved, cryptographers cannot be sure computationally intractable problems exist. Cryptographers thus make assumptions as to which problems are ''hard''. It is commonly believed that if ''m'' is the product of two large primes, then calculating φ(''m'') is currently computationally infeasible; this assumption is required for the security of the RSA Cryptosystem. The Φ-Hiding assumption is a stronger assumption, namely that if ''p''1 and ''p''2 are small primes exactly one of which divides φ(''m''), there is no polynomial-time algorithm which can distinguish which of the primes ''p''1 and ''p''2 divides φ(''m'') with probability significantly greater than one-half. This assumption was first stated in the 1999 paper Computationally Private Information Retrieval with Polylogarithmic Communication. ==Applications== The Phi-hiding assumption has found applications in the construction of a few cryptographic primitives. Some of the constructions include: *(Computationally Private Information Retrieval with Polylogarithmic Communication ) (1999) *(Efficient Private Bidding and Auctions with an Oblivious Third Party ) (1999) *(Single-Database Private Information Retrieval with Constant Communication Rate ) (2005) *(Password authenticated key exchange using hidden smooth subgroups ) (2005) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Phi-hiding assumption」の詳細全文を読む スポンサード リンク
|